package _11_整理题目._2_二叉树_递归_dfs_bfs._递归._生成二叉树;

import org.junit.Test;
import util.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 * 
 * 递归构建二叉树
 * 1、确定 递归函数的输入参数和返回值
 *      由题目，根据 pre[] 和 in[] 构建，返回 TreeNode
 * 2、确定 递归函数的终止条件
 *      传入的是数组，可根据 pre/in.length() == 0 来终止
 * 3、编写 递归创建二叉树逻辑
 *      先根据 pre[0] 的值 创建根节点 root
 *      再遍历 in[] 中找到 根节点pre[0] 的下标 分出 左子树 和 右子树 的下标范围
 *      生成左子树 root.left  = pre 中左子树的下标范围，in 中左子树的下标范围;
 *      生成右子树 root.right = pre 中右子树的下标范围，in 中右子树的下标范围;
 *      注意 Arrays.copyOfRange(int[], from, to) 复制是范围是 左闭右开
 * 
 */
public class _04_根据前序中序重建二叉树 {
    
    Map<Integer, Integer> map = new HashMap<>();
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0; i<inorder.length; i++) {
            map.put(inorder[i], i);
        }
        TreeNode root = dfs(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
        return root;
    }
    
    public TreeNode dfs(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
        if(preLeft > preRight || inLeft > inRight) return null;
        
        TreeNode root = new TreeNode(preorder[preLeft]);
        int rootIndex = map.get(preorder[preLeft]);
        int size = rootIndex - inLeft;
        root.left = dfs(preorder, inorder, preLeft+1, preLeft+size, inLeft, rootIndex-1);
        root.right = dfs(preorder, inorder, preLeft+size+1, preRight, rootIndex+1, inRight);
        return root;
    }
    
    @Test
    public void main() {
        int[] pre = {1,2,4,5,3,6,7};
        int[] in  = {4,2,5,1,6,3,7};
        TreeNode root = buildTree(pre, in);
        TreeNode.printTree(root);
    }
    
}
